#include <iostream>
#include <google_hash/sparse_hash_map>
#include <google_hash/dense_hash_map>
#include <hash/cuckoo.hpp>
#include <map>
#include <hash_map>
#include <vector>
#include <list>

#include <hash/topk.h>


using google::sparse_hash_map;      // namespace where class lives by default
using google::dense_hash_map;
using std::cout;
using std::endl;
using __gnu_cxx::hash;  // or __gnu_cxx::hash, or maybe tr1::hash, depending on your OS

struct eqstr
{
  bool operator() (const char* s1, const char* s2) const
  {
    return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

struct ltstr
{
  bool operator () (const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

void test_sparse_hash_map();
void test_dense_hash_map();
void test_multimap();
void test_hash_multimap();
void test_cuckoo_map();

int main()
{
  test_sparse_hash_map();
  test_dense_hash_map();
  test_multimap();
  test_hash_multimap();
  test_cuckoo_map();
}

template<typename Key>
class Hasher
{
public:
  unsigned int operator () (Key key, size_t i) const
  {
    hash<Key> h_;
    return (h_(key) + i * rand()) % RAND_MAX;
  }
};

void lookup(const cuckoo<const char*, std::list<int>, Hasher<const char*>, eqstr>& Map, const char* str)
{
  cout << str << ": ";
  cuckoo<const char*, std::list<int>, Hasher<const char*>, eqstr>::const_iterator p = Map.find(str);
  if(p != Map.end())
  {
    for(std::list<int>::const_iterator j = (*p).second.begin(); j != (*p).second.end(); ++j)
      cout << *j << " ";
  }
  cout << endl;
}

void test_cuckoo_map()
{
  cuckoo<const char*, std::list<int>, Hasher<const char*>, eqstr> m;

  m["a"].push_back(1);
  m["c"].push_back(2);
  m["b"].push_back(3);
  m["b"].push_back(4);
  m["a"].push_back(5);
  m["b"].push_back(6);

  lookup(m, "a");
  lookup(m, "b");
  lookup(m, "c");
  lookup(m, "d");
  cout << endl;

}

void lookup(const sparse_hash_map<const char*, std::list<int>, hash<const char*>, eqstr>& Map, const char* str)
{
  cout << str << ": ";
  sparse_hash_map<const char*, std::list<int>, hash<const char*>, eqstr>::const_iterator p = Map.find(str);
  if(p != Map.end())
  {
    for(std::list<int>::const_iterator j = (*p).second.begin(); j != (*p).second.end(); ++j)
      cout << *j << " ";
  }
  cout << endl;
}


void test_sparse_hash_map()
{
  sparse_hash_map<const char*, std::list<int>, hash<const char*>, eqstr> m;

  m["a"].push_back(1);
  m["c"].push_back(2);
  m["b"].push_back(3);
  m["b"].push_back(4);
  m["a"].push_back(5);
  m["b"].push_back(6);

  lookup(m, "a");
  lookup(m, "b");
  lookup(m, "c");
  lookup(m, "d");
  cout << endl;
}


void lookup(const dense_hash_map<const char*, std::list<int>, hash<const char*>, eqstr>& Map, const char* str)
{
  cout << str << ": ";
  dense_hash_map<const char*, std::list<int>, hash<const char*>, eqstr>::const_iterator p = Map.find(str);
  if(p != Map.end())
  {
    for(std::list<int>::const_iterator j = (*p).second.begin(); j != (*p).second.end(); ++j)
      cout << *j << " ";
  }
  cout << endl;

}

void test_dense_hash_map()
{
  dense_hash_map<const char*, std::list<int>, hash<const char*>, eqstr> m;

  m.set_empty_key(NULL);

  m["a"].push_back(1);
  m["c"].push_back(2);
  m["b"].push_back(3);
  m["b"].push_back(4);
  m["a"].push_back(5);
  m["b"].push_back(6);

  lookup(m, "a");
  lookup(m, "b");
  lookup(m, "c");
  lookup(m, "d");
  cout << endl;

}

void lookup(const std::multimap<const char*, int, ltstr>& Map, const char* str)
{
  cout << str << ": ";
  std::pair<std::multimap<const char*, int, ltstr>::const_iterator, std::multimap<const char*, int, ltstr>::const_iterator> p = Map.equal_range(str);
  for(std::multimap<const char*, int, ltstr>::const_iterator i = p.first; i != p.second; ++i)
    cout << (*i).second << " ";
  cout << endl;
}

void test_multimap()
{
  std::multimap<const char*, int, ltstr> m;

  m.insert(std::pair<const char* const, int>("a", 1));
  m.insert(std::pair<const char* const, int>("c", 2));
  m.insert(std::pair<const char* const, int>("b", 3));
  m.insert(std::pair<const char* const, int>("b", 4));
  m.insert(std::pair<const char* const, int>("a", 5));
  m.insert(std::pair<const char* const, int>("b", 6));

  lookup(m, "a");
  lookup(m, "b");
  lookup(m, "c");
  lookup(m, "d");
  cout << endl;
}

void lookup(const __gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>& Map, const char* str)
{
  cout << str << ": ";
  std::pair<__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::const_iterator, __gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::const_iterator> p =
    Map.equal_range(str);
  for (__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::const_iterator i = p.first; i != p.second; ++i)
    cout << (*i).second << " ";
  cout << endl;
}

void test_hash_multimap()
{
  __gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr> m;

  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("a", 1));
  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("c", 2));
  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("b", 3));
  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("b", 4));
  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("a", 5));
  m.insert(__gnu_cxx::hash_multimap<const char*, int, hash<const char*>, eqstr>::value_type("b", 6));

  lookup(m, "a");
  lookup(m, "b");
  lookup(m, "c");
  lookup(m, "d");
  cout << endl;
}
